BIT Algo/3. Zajęcia/Zadanie 8. (Liczba różnych elementów z tablicy A o różnicy równej k).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Dana jest tablica $ A $ oraz liczba $ k $. Napisz program, który znajduje liczbę różnych par elementów z tablicy $ A $ o różnicy równej $ k $. <br> Przykład: Dla tablicy:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    [7, 11, 3, 7, 3, 9, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### oraz $ k = 4 $ odpowiedzią jest liczba 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "W pierwszej kolejności, jak prawie zawsze, musimy posortować tablicę. Najlepiej użyć do tego celu algorytm Quick Sort, ponieważ nie wiemy nic na temat liczb, jakie znajdują się w tablicy. W kolejnym kroku wystarczy przejść liniowo po tablicy, przechodząc pierwszym wskaźnikiem po kolejnych elementach i odpowiednio przesuwając drugi wskaźnik. Ponieważ interesują nas różne pary elementów, konieczne jest tylko jednorazowe sprawdzenie różnicy dla danej pary wartości, więc jeżeli trafimy na taką wartość, że poprzednia była identyczna, musimy przesunąć pierwszy wskaźnik na następną wartość, różną od poprzedniej. W następnym kroku konieczne jest sprawdzenie, czy różnica pomiędzy elementem, na który wskazuje pierwszy wskaźnik, a elementem, wskazywanym przez drugi wskaźnik, jest odpowiednia. Istnieje duże prawdopodobieństwo, że po przesunięciu pierwszego wskaźnika na nową wartość, różnica będzie zbyt duża, więc musimy również przesuwać drugi wskaźnik, do momentu, w którym różnica będzie nie większa niż $ k $. Po zakończeniu przesuwania drugiego wskaźnika, konieczne jest sprawdzenie, czy różnica między elementem wskazywanym przez pierwszy wskaźnik, a elementem wskazywanym przez drugi wskaźnik, jest równa $ k $. Jeżeli tak, to zwiększamy licznik unikatowych par o 1, a w przeciwnym razie, przesuwamy pierwszy wskaźnik dalej i zaczynamy ponownie sprawdzanie od początku."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# no - number of ...\n",
    "def no_unique_pairs(arr, k):\n",
    "    if len(arr) < 2: return -1\n",
    "    # Sort an array of values\n",
    "    quick_sort(arr)\n",
    "    # Count all unique pairs of values\n",
    "    pairs_count = 0\n",
    "    # Count pairs in a loop using a Binary Search algorithm\n",
    "    j = 0\n",
    "    i = 1    \n",
    "    while i < len(arr):\n",
    "        # Skip repeated values\n",
    "        while i < len(arr) - 1 and arr[i] == arr[i-1]:\n",
    "            i += 1\n",
    "        # Move j pointer till a dfference between arr[i] and arr[j] is too large\n",
    "        while j < i and arr[i] - arr[j] > k:\n",
    "            j += 1\n",
    "        # Check if a difference between two values is equal to k\n",
    "        if arr[i] - arr[j] == k:\n",
    "            pairs_count += 1\n",
    "        # Advance a pointer\n",
    "        i += 1\n",
    "    # Return a total number of pairs\n",
    "    return pairs_count\n",
    "\n",
    "\n",
    "def quick_sort(arr):\n",
    "    _quick_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quick_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        pivot_position = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        if pivot_position - left_idx < right_idx - pivot_position:\n",
    "            _quick_sort(arr, left_idx, pivot_position)\n",
    "            left_idx = pivot_position + 1  # I removed a tailing recursion\n",
    "        else:\n",
    "            _quick_sort(arr, pivot_position + 1, right_idx)\n",
    "            right_idx = pivot_position  # I removed a tailing recursion\n",
    "        \n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 2 subarrays of elements lower than or\n",
    "    # equal to a pivot and of elements greater or equal to a pivot \n",
    "    # (in this partition algorithm pivot isn't placed on a fixed position \n",
    "    # but can be also swapped like all the remaining values)\n",
    "    i = left_idx - 1\n",
    "    j = right_idx + 1\n",
    "    while True:\n",
    "        i += 1\n",
    "        while arr[i] < pivot: i += 1\n",
    "            \n",
    "        j -= 1\n",
    "        while arr[j] > pivot: j -= 1\n",
    "        \n",
    "        if i < j:\n",
    "            _swap(arr, i, j)\n",
    "        else:\n",
    "            return j  # Return a pivot position after the last swap\n",
    "\n",
    "    \n",
    "def _swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "[3, 3, 3, 3, 5, 5, 5, 7, 7, 7, 7, 9, 11]\n"
     ]
    }
   ],
   "source": [
    "arr = [7, 11, 3, 3, 3, 5, 5, 7, 7, 7, 3, 9, 5]\n",
    "# arr = [7, 11, 3, 7, 3, 9, 5]\n",
    "k = 4\n",
    "\n",
    "print(no_unique_pairs(arr, k))\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "[7, 7]\n"
     ]
    }
   ],
   "source": [
    "arr = [7, 7]\n",
    "k = 0\n",
    "\n",
    "print(no_unique_pairs(arr, k))\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "[7, 7, 7, 7, 7]\n"
     ]
    }
   ],
   "source": [
    "arr = [7, 7, 7, 7, 7]\n",
    "k = 0\n",
    "\n",
    "print(no_unique_pairs(arr, k))\n",
    "print(arr)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}